
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1604. -- [Usaco2008 Open]Cow Neighborhoods -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1604: [Usaco2008 Open]Cow Neighborhoods</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>133&nbsp;&nbsp;<span class=green>Solved: </span>50<br>[<a href='submitpage.php?id=1604'>Submit</a>][<a href='problemstatus.php?id=1604'>Status</a>][<a href='bbs.php?id=1604'>Discuss</a>]</center><h2>Description</h2><div class=content>Those Who Know About Cows are aware of the way cows group into "Cow 
Neighborhoods". They have observed Farmer John's N (1 <= N <= 
100,000) cows (conveniently numbered 1..N) as they graze, each at 
her own unique integer rectilinear coordinate, on a pasture whose 
X and Y coordinates are in the range 1..1,000,000,000. 

Two cows are neighbors if at least one of two criteria is met: 

1) If the cows are no further than some integer Manhattan distance 
C (1 <= C <= 1,000,000,000) apart, they are neighbors. [Manhattan 
distance is calculated as d = |x1-x2| + |y1-y2|.] 

2) If cow A is a neighbor of cow Z and cow B is a neighbor of cow 
Z, then cow A is a neighbor of cow B (the "transitive closure 
of neighbors"). 

Given the locations of the cows and the distance C, determine the 
the number of neighborhoods and the number of cows in the largest 
neighborhood. 

By way of example, consider the pasture below. When C = 4, this 
pasture has four neighborhoods: a big one on the left, two neighborhoods 
of size 1 (the lonesome cows), and a huge neighborhood on the right 
with 60 different cows. 

.....................................*................. 
....*...*..*.......................***................. 
......*...........................****................. 
..*....*..*.......................*...*.******.*.*..... 
........................*.............***...***...*.... 
*..*..*...*..........................*..*...*..*...*... 
.....................................*..*...*..*....... 
.....................................*..*...*..*....... 
...*................*.................................. 
.*..*............................*.*.*.*.*.*.*.*.*.*.*. 
.*.....*..........................*.*.*.*.*.*.*.*.*.*.* 
....*.................................................. 

The input file describes cow locations by integer X,Y coordinates, 
where the lower left corner is (1,1) and cows close to that corner 
appear at both (2,2) and (5,1) in the example above. 

For a given pasture, determine both the number of cow neighborhoods 
and the number of cows resident in the largest cow neighborhood. 

The above picture is sample test case 2, which will be evaluated 
for you upon submission. 

Partial feedback for some test cases will be provided on the first 
10 submissions. 

给出N头牛的坐标，以及一个常数C 
两头牛A和B满足下面两个条件中至少一个，便是邻居 
1：两者之间的距离小于C,距离为计算为两者横纵坐标差的绝对差 
2：存在奶牛C，便奶牛A和C是邻居，奶牛B和C也是邻居， 

请找出有多少个奶牛群，以及最大的群中有多少头牛.

</div><h2>Input</h2><div class=content>* Line 1: Two space-separated integers: N and C 
* Lines 2..N+1: Line i+1 describes cow i's location with two 
space-separated integers: X_i and Y_i 
</div><h2>Output</h2><div class=content>* Line 1: A single line with a two space-separated integers: the 
number of cow neighborhoods and the size of the largest cow 
neighborhood. 

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>4 2<br />
1 1<br />
3 3<br />
2 2<br />
10 10<br />
<br />
* Line 1: A single line with a two space-separated integers: the<br />
        number of cow neighborhoods and the size of the largest cow<br />
        neighborhood.<br />
<br />
<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>2 3<br />
<br />
OUTPUT DETAILS:<br />
There are 2 neighborhoods, one formed by the first three cows and<br />
the other being the last cow. The largest neighborhood therefore<br />
has size 3.<br />
<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1604'>Submit</a>][<a href='problemstatus.php?id=1604'>Status</a>][<a href='bbs.php?id=1604'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
